package com.johann.leetcode;

import java.util.*;

public class T5_LongestPalindrome {
    public static class Solution{
        // 暴力筛选 超时
        public String longestPalindrome01(String s) {
            if (s.length()<=1) {
                return s;
            }
            int len = s.length();
            int maxLen = 1;
            Map<Integer,String> strArr = new HashMap<>();
            List<String> arr = new ArrayList<>();
            // 双层循环
            for (int i = 0; i < len; i++) {
                for (int j = i+1; j < len; j++) {
                    if (isPalindrome(s,i,j)) {
                        //左闭右开区间
                        strArr.put(j-i+1,s.substring(i,j+1));
                        arr.add(s.substring(i,j+1));
                    }
                }
            }
            //如果数据一个都不重复,那么他的任意一个数都是回文数
            if (arr.isEmpty()) {
                return s.substring(0,1);
            }
            for (String s1 : arr) {
                maxLen = Math.max(maxLen, s1.length());
            }
            return strArr.get(maxLen);
        }
        private boolean isPalindrome(String s,int x,int y){
            for (int i = x,j=y; i <=j ; i++,j--) {
                if (s.charAt(i) != s.charAt(j)) {
                    return false;
                }
            }
            return true;
        }


    }

    public static void main(String[] args) {
        String s = "aacabdkacaa";
        System.out.println(new Solution().longestPalindrome01(s));
    }
}
